\chapter{Introdução}

As implementações de linguagens de programação dividem-se em três
classes ao
considerar o produto final de seus compiladores e demais
ferramentas envolvidas no processo de tradução. A primeira classe
envolve linguagens que realizam exclusivamente compilação até
chegar-se a código executável, a segunda engloba aquelas que
unicamente interpretam o código fonte. A terceira classe, a mais
flexível, contem aquelas que operam em um modo misto (ou híbrido).
Linguagens que, de alguma forma,
realizam tradução em tempo de execução fazem parte deste último modo.
A compilação híbrida está diretamente ligada a este
trabalho.

Essa divisão em classes está relacionada com o avanço da computação,
pois este propiciou
a criação de linguagens de mais alto nível que, apesar de
terem desempenho inferior à linguagens de baixo nível,
são viáveis de se utilizar. Também há uma ligação entre a facilidade e a
criação de programas mais complexos, incentivando linguagens que visam
portabilidade entre sistemas e rapidez de desenvolvimento sem
que sejam necessariamente compiladas (primeira classe).
Considerando-se tempo de execução e
consumo de memória, é esperado que um programa ganhe
nesses quesitos quando implementado numa linguagem da primeira
classe. Por essa razão, os primeiros compiladores,
devido aos recursos existentes na época, limitavam-se a esta
forma e as linguagens ainda não se preocupavam com facilidade de uso.
Mas, com o surgimento de programas maiores, viu-se a necessidade de
fornecer ao usuário a chance de interagir com o sistema de forma
simplificada. %falar alguma coisa em relação a facilidade dessa interação?
No caso do
sistema operacional UNIX, isto ocorreu por meio da criação de
um \textit{shell} que funciona puramente como um interpretador.
%\cite{ksh} -- não.

A interpretação por parte das linguagens sacrifica desempenho em
favor de um alto nível de abstração, possibilitando maior
expressividade, facilidade de
desenvolvimento, portabilidade, flexibilidade e dinamicidade, entre
outras características.

De maneira semelhante ao \textit{shell} do UNIX,
a linguagem de programação \texttt{Tcl} (\textit{Tool Command Language})
\nomenclature{Tcl}{Tool Command Language}
teve como principal objetivo a
facilidade de incorporação (\textit{embedding}) a aplicações que
necessitassem de uma linguagem de comandos para
interação com usuários \cite{ousterhout_89}.
Na época não havia um
incentivo computacional para utilizar este tipo de linguagem de forma
ampla e, assim, o custo despendido pela interpretação não tinha
impacto sobre o sistema maior, pois os programas criados com estas linguagens
tendiam a ser bastante curtos. O autor da \texttt{Tcl} chegou a dizer
que ``... quase todos ``programas'' em \texttt{Tcl} serão curtos,
muitos de apenas uma linha. A maioria dos programas serão escritos,
executados uma vez ou talvez poucas vezes e, então,
descartados. ...'' \cite{ousterhout_89}.

Com a evolução da capacidade computacional, as linguagens
puramente interpretadas começaram a ser utilizadas em maior
escala e o custo envolvido tornou-se mais óbvio.
Começaram a surgir aplicativos desenvolvidos com a
\texttt{Tcl} contendo milhares de linhas,
como, por exemplo, exmh \cite{exmh}, OpenACS \cite{openacs} ou mesmo o
\textit{benchmark} de testes do GDB (\textit{GNU Debugger})
\nomenclature{GDB}{GNU Debugger}
\cite{gdb_testsuite}.
Com isso, problemas relacionados ao desempenho tornaram-se reais.
A ``solução'' inicial
encontrada para a \texttt{Tcl} foi a
reescrita de trechos críticos na
linguagem \texttt{C} \cite{krbook}, visto que a \texttt{Tcl}
disponibiliza uma interface para a mesma. Entretanto, com isto perde-se
benefícios como gerenciamento de memória automático e maior facilidade
de desenvolvimento -- características comuns dessas linguagens.
Por esta razão, os implementadores têm
buscado melhorar a performance de linguagens interpretadas.

Uma maneira de melhorar o desempenho da linguagem, sem retirar suas
vantagens, envolve o uso do modo
misto de compilação. As linguagens \texttt{Java} \cite{javaspec} e
\texttt{Python} \cite{pythonspec} por meio do Psyco \cite{psyco} são exemplos
que fazem uso desta técnica, mas somente a primeira dessas
atualmente consegue não depender de reescrita em outras linguagens
para alcançar uma boa performance para os mais variados tipos
de aplicações.
%Por esta razão, um modo misto de compilação vem sendo utilizado em
%linguagens de programação como \texttt{Java} ou \texttt{Python}, e
%desde 1996 em \texttt{Tcl} \cite{tcl_bytecode}.

A definição da terceira classe de implementações de linguagem,
envolvendo compilação
mista, têm sido vaga. Isso é reflexo do que é possível nesse
modo. Poder-se-ia considerar a linguagem \texttt{Java} e uma
implementação da JVM (\textit{Java Virtual Machine}) \cite{jvmspec}
\nomenclature{JVM}{Java Virtual Machine}
que trabalha com \textit{bytecodes} e também permite compilação JIT
(\textit{Just-In-Time}) \nomenclature{JIT}{Just-In-Time}
para código de máquina. Após realizar a
tradução de código fonte para \textit{bytecodes}, a máquina virtual
pode iniciar sua execução e interpretar essa forma de código.
É possível que, durante a execução do programa,
de acordo com critérios estabelecidos, os \textit{bytecodes} venham a
ser propriamente convertidos em código de máquina e ajustados no
ambiente de execução de forma
a possibilitar sua execução direta sem uso de um interpretador.
Mas esta situação cobre uma única possibilidade, deixando outras de fora.
% XXX
% Estas são duas formas de trabalhar com compilação mista, mas elas não
% caracterizam todas as possibilidades.

De forma geral, JIT refere-se a tradução de código sob demanda. Isso
possibilita que o trabalho de \citeonline{tcl_bytecode} -- responsável
por efetivamente trazer o modo misto para a \texttt{Tcl} -- seja descrito
como um sistema JIT para a \texttt{Tcl}, pois a conversão de código
fonte para \textit{bytecodes} ocorre somente durante a chamada de
procedimentos que ainda não tenham sido ``\textit{byte}-compilados''
ou que tenham sofrido alguma alteração entre chamadas. Ou seja, por
assim ocorrer, na
\texttt{Tcl} a compilação para \textit{bytecodes} é dita ser feita
\textit{online} ao invés de
\textit{offline} como no caso da JVM
mencionada acima. Ainda assim, não
há a conversão para código de máquina em momento algum. Neste
trabalho, o interesse está especificamente em tratar esta situação.

A compilação dinâmica (ou JIT) pode fazer uso de informações produzidas
pelo programa em execução para guiar o processo de compilação. Com
isso, linguagens tipicamente difíceis de serem analisadas e compiladas
estaticamente, devido a uso de, por exemplo, tipos e/ou
escopo dinâmico \cite{holzle}, % Holzle fala sobre isso na parte 5.1
 ganham a oportunidade de melhoria de desempenho com
o uso de tal sistema de compilação. Esta técnica tornou-se mais popular a
partir de diversas implementações de JVM, como a
CACAO \cite{cacao}, JUDO \cite{judo},
Jalapeño (Jikes RVM (\textit{Research Virtual
  Machine})) \nomenclature{RVM}{Research Virtual Machine}
\cite{jalapeno_1} e também a IBM \textit{Development Kit}
\cite{suganuma_ibm}, que reportaram resultados
significantes na redução de tempo de execução quando comparado a um
interpretador de \textit{bytecodes}. Outras linguagens também têm
recebido esforços nessa direção. Um dos primeiros trabalhos foi o de
\citeonline{deutsch84efficient} para a \texttt{Smalltalk}; a
linguagem \texttt{Self} contou com a implementação SELF-93, descrita
no trabalho de \citeonline{holzle} e contribuiu para JVMs criadas mais
tarde; para o
\texttt{Python} há o Psyco
\cite{psyco} e mais recentemente também a \textit{Unladen Swallow}
que faz uso da LLVM \cite{llvm1}
\nomenclature{LLVM}{Low Level Virtual Machine}.
Todos estes trabalhos têm em comum,
além do uso de compilação dinâmica, o uso de
compiladores otimizadores.

Um compilador JIT requer que as estruturas internas sejam
suficientemente eficientes, caso contrário torna-se inviável o
uso do compilador em tempo de execução. As escolhas a
cerca de quais representações intermediárias utilizar, como estruturar
os dados, quais otimizações aplicar e algoritmos para diversas fases da
compilação, devem ser feitas de forma a conseguir balancear baixo
tempo de compilação com código gerado de alta qualidade. Ainda há o
quesito de consumo de memória principal, que, apesar da crescente
capacidade disponível, ainda costuma ser um recurso escasso em
dispositivos embarcados. Sabe-se que o interpretador \texttt{Tcl} está
presente em roteadores da Cisco \cite{cisco}, pois vem incluso no Cisco IOS
(\textit{Internetwork Operating Systems}) \cite{cisco_ios}, mas esse trabalho
não tem como foco tal tipo de dispositivo e, portanto, o consumo de
memória não será um dos pontos levados em consideração.

Um fator importante durante o desenvolvimento de sistemas deste porte
é a sua manutenibilidade. Um nível muito alto de abstração,
impediria a utilização de uma aplicação de desempenho crítico.
Por outro lado, um nível muito baixo dificultaria a correção/detecção de
problemas e melhorias gerais.
Uma alternativa para esse problema vem sendo desenvolvida no
projeto PyPy \cite{pypy}, onde um interpretador para uma linguagem
qualquer é escrito em \texttt{RPython} \cite{rpython} (uma implementação
restrita da linguagem \texttt{Python}) e o PyPy realiza a tradução do
mesmo para a
linguagem \texttt{C} incluindo (atualmente) juntamente um compilador
JIT. Entretanto, um
dos objetivos do trabalho discutido aqui é analisar como um sistema de
tamanho reduzido compete com sistemas mais robustos. Não se tem a
intenção de fornecer um ambiente de alto nível para construção de
outras máquinas virtuais com ou sem compiladores JIT para
\texttt{Tcl}, mas sim uma implementação específica e direta.
A escolha da
linguagem \texttt{C} reflete esse objetivo porque não adiciona novas
dependências ao núcleo da linguagem \texttt{Tcl} além de possibilitar
criação de programas com desempenho aceitável.

Apesar da linguagem \texttt{Tcl} ainda não ter recebido um compilador
JIT que destina-se a produzir código nativo, o trabalho por
\citeonline{vitale_catenation} lida
com a eliminação do \textit{overhead} de decodificação dos
\textit{bytecodes}, introduzido pelo trabalho de \citeonline{tcl_bytecode},
fazendo uso de \textit{templates} que contém as instruções em
código nativo utilizadas para interpretar cada \textit{bytecode}.
Esse código é
obtido por meio da compilação do próprio interpretador
\texttt{Tcl} e cada \textit{template} é copiado múltiplas vezes,
numa área de memória alocada em tempo de execução, conforme a quantidade de
cada \textit{bytecode} gerado. Nesse mesmo trabalho, o interpretador foi
modificado de forma a executar somente o código formado pela
concatenação de \textit{templates}, eliminando o \textit{overhead} de
decodificação. Demonstrou-se que em certos casos o desempenho da
linguagem pode melhorar em até 60\% com a aplicação dessa técnica.
Esse trabalho é provavelmente o mais próximo, quando considerando
somente a \texttt{Tcl}, do que se pretende produzir aqui.
Mas ele não gera código, apenas copia código já gerado por um compilador
estático e replica conforme necessário, fazendo os devidos
ajustes, em tempo de execução. Por um lado o tempo de ``compilação'' é
bastante baixo, porém, não dá espaço para técnicas de otimização,
limitando o potencial de melhoria de desempenho para trabalhos futuros.

O presente trabalho propõe uma implementação inicial de um compilador
JIT não-otimizador para um subconjunto da linguagem \texttt{Tcl},
focando-se no trabalho com números. O
propósito é obter um tempo de decodificação e interpretação
reduzido em relação ao da máquina virtual da mesma. Espera-se que o nível de
simplicidade, manutenibilidade e flexibilidade atingidos possam
permitir extensões e desenvolvimentos futuros sobre este trabalho inicial.
A arquitetura IA-32 \cite{intel_basicarch} foi escolhida como alvo,
pois está presente em boa
parte dos computadores de uso pessoal. Embora a linguagem \texttt{Tcl}
atualmente execute em outras arquiteturas, como IA-64
\cite{intel_basicarch} e ARM \cite{arm_arch}, pretendeu-se alcançar um
nível de simplicidade que permita a portabilidade do sistema sem
tornar a tarefa demasiadamente complexa. Para a representação
intermediária, este trabalho fez uso de
quádruplas \cite{muchnick}, que são utilizadas para formar
blocos básicos e
construir grafos de fluxo de controle (CFG -- \textit{Control Flow
  Graph}) \nomenclature{CFG}{Control Flow Graph}.
Esta representação é de nível médio e
o CFG é diretamente utilizado na geração de código de máquina.

O Capítulo \ref{compdyn} apresenta conceitos da compilação dinâmica e
realiza uma revisão bibliográfica descrevendo trabalhos que, de alguma
forma, influenciaram o desenvolvimento deste compilador JIT.

O Capítulo \ref{tcljit} inicia com uma descrição da linguagem
\texttt{Tcl} e, em seguida, descreve a estrutura e o funcionamento do
compilador JIT desenvolvido.

No Capítulo \ref{avaliacao} são apresentados dados coletados que
validam de forma experimental o desempenho alcançado. Os resultados
obtidos demonstram até cerca de 29 vezes de redução de tempo de
execução em relação ao interpretador da \texttt{Tcl}.

E, por fim, o Capítulo \ref{conclusao} apresenta as conclusões e os
trabalhos futuros.
